package org.algorithm.熊猫;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/***
 * @Task 2022/2/21
 * @Link  {https://leetcode-cn.com/problems/lru-cache/}
 */
public class LRUCacheTest {

    @Test
    public void test() {
        LRUCache map = new LRUCache(2);
        map.put(1, 1);
        map.put(2, 2);
        int i = map.get(1);
        map.put(3, 3);
        int i1 = map.get(2);
        System.out.println(i1);
    }

    class LRUCache {
        Map<Integer, MyLinkedNode> cach = new HashMap<Integer, MyLinkedNode>();
        private int size;

        private int capacity;

        private MyLinkedNode head;

        private MyLinkedNode tail;


        public LRUCache(int capacity) {
            size = 0;
            this.capacity = capacity;
            head = new MyLinkedNode();
            tail = new MyLinkedNode();
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            MyLinkedNode myLinkedNode = cach.get(key);
            if (myLinkedNode == null) {
                return -1;
            }
            //迁移
            moveToHead(myLinkedNode);
            return myLinkedNode.value;
        }


        public void put(int key, int value) {
            MyLinkedNode node = cach.get(key);
            if (node == null) {
                //添加
                MyLinkedNode nodeNew = new MyLinkedNode(key, value);
                cach.put(key, nodeNew);
                addHead(nodeNew);
                ++size;
                if (size > capacity) {
                    MyLinkedNode pre = tail.pre;
                    removeNode(pre);
                    cach.remove(pre.key);
                    --size;
                }

            } else {
                //存在，更换位置
                node.value = value;
                moveToHead(node);
            }
        }


        /**
         * 移动元素
         *
         * @param myLinkedNode
         */
        private void moveToHead(MyLinkedNode myLinkedNode) {
            //删除当前元素
            removeNode(myLinkedNode);
            //添加到头部
            addHead(myLinkedNode);
        }

        /**
         * 将元素添加到头部
         *
         * @param myLinkedNode
         */
        private void addHead(MyLinkedNode myLinkedNode) {
            myLinkedNode.pre = head;
            myLinkedNode.next = head.next;
            head.next.pre = myLinkedNode;
            myLinkedNode.next = myLinkedNode;
        }

        /**
         * 删除当前元素
         *
         * @param myLinkedNode
         */
        private void removeNode(MyLinkedNode myLinkedNode) {
            myLinkedNode.pre.next = myLinkedNode.next;
            myLinkedNode.next.pre = myLinkedNode.pre;
        }

        class MyLinkedNode {
            int key;
            int value;
            MyLinkedNode pre;
            MyLinkedNode next;

            public MyLinkedNode() {
            }

            public MyLinkedNode(int key, int value) {
                this.key = key;
                this.value = value;
            }

        }
    }


}
